package com.lw.leetcode.tree.b;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * tree
 * 面试题 16.20. T9键盘
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/1 13:30
 */
public class GetValidT9Words {

    private int[][] arr = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {9, 10, 11}, {12, 13, 14}, {15, 16, 17, 18}, {19, 20, 21}, {22, 23, 24, 25}};
    private List<String> list = new ArrayList<>();

    public List<String> getValidT9Words(String num, String[] words) {
        Node root = new Node();
        for (String word : words) {
            add(word, 0, root);
        }
        find(num, 0, root, new StringBuilder());
        return list;
    }

    private void find(String str, int index, Node node, StringBuilder sb) {
        if (str.length() == index) {
            list.add(sb.toString());
            return;
        }
        int[] ints = arr[str.charAt(index) - 50];
        for (int anInt : ints) {
            if (node.nodes[anInt] != null) {
                sb.append((char) (anInt + 'a'));
                find(str, index + 1, node.nodes[anInt], sb);
                sb.setLength(index);
            }
        }
    }

    private void add(String str, int index, Node node) {
        if (str.length() == index) {
            return;
        }
        int i = str.charAt(index) - 'a';
        if (node.nodes[i] == null) {
            node.nodes[i] = new Node();
        }
        add(str, index + 1, node.nodes[i]);
    }

    class Node {
        private Node[] nodes = new Node[26];
    }

}
